//
// Created by liushuai on 2020/4/1.
//
#include "rob.h"
<<<<<<< HEAD
int rob(vector<int> &nums) {
  int size = nums.size();
  int result = 0;
  if (size == 0)
    return 0;
  else if (size == 1)
    return nums.at(0);
  else if (size == 2)
    return max(nums.at(0), nums.at(1));
  else {
    int start = 2;
    int lower = nums.at(0);
    int upper = max(nums.at(0), nums.at(1));
    while (start < size) {
      result = max(lower + nums.at(start), upper);
      lower = upper;
      upper = result;
      start++;
    }
    return result;
  }
}
int rob1(vector<int> &nums) {
  int dp[2] = {0, 0};
  int size = nums.size();
  if (size == 1)
    dp[1] = nums[0];
  else if (size >= 2) {
    dp[1] = nums[0];
    for (int i = 2; i < nums.size() + 1; i++) {
      int max_value = nums[i - 1] + dp[0] > dp[1] ? nums[i - 1] + dp[0] : dp[1];
      dp[0] = dp[1];
      dp[1] = max_value;
    }
  }
  return dp[1];
=======
int robRecursive(vector<int> &nums, const unsigned int N) {
  if (N == 0)
    return nums.at(0);
  else if (N == 1) {
    return std::max(nums.at(0), nums.at(1));
  } else {
    return std::max(robRecursive(nums, N - 1),
                    robRecursive(nums, N - 2) + nums.at(N));
  }
}
// robrecursive递归超时
int robRecursive(std::vector<int> &nums) {
  return robRecursive(nums, nums.size() - 1);
}

int rob(std::vector<int> &nums) {
  int dp[2] = {0, 0};
  int n = nums.size();
  int i = 1;
  for (; i <= n; i++) {
    if (i == 1) {
      dp[i % 2] = nums[0];
    } else if (i == 2) {
      dp[i % 2] = std::max(nums.at(0), nums.at(1));
    } else {
      dp[i % 2] = std::max(dp[i % 2] + nums.at(i - 1), dp[(i - 1) % 2]);
    }
  }
  return dp[n % 2];
>>>>>>> dev
}
